class Solution:
    def integerBreak(self, n: int) -> int:
        if n <= 2: return 1
        dp = [1] * (n + 1)
        for i in range(2, n + 1):
            for j in range(1, i // 2 + 1):
                dp[i] = max([dp[i], dp[j] * dp[i - j], dp[j] * (i - j), j * dp[i - j], j * (i - j)])
        return dp[-1]


if __name__ == '__main__':
    s = Solution()
    r = s.integerBreak(10)
    print(r)
